/**
 * 版权所有 2009-2012山东新北洋信息技术股份有限公司
 * 保留所有权利。
 */
package com.linyaonan.leetcode.medium._429;

import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;
import java.util.Queue;

/**
 *
 * 给定一个 N 叉树，返回其节点值的层序遍历。 (即从左到右，逐层遍历)。
 *
 * 例如，给定一个 3叉树 :
 *
 * 返回其层序遍历:
 *
 * [
 *      [1],
 *      [3,2,4],
 *      [5,6]
 * ]
 *  
 *
 * 说明:
 *
 * 树的深度不会超过 1000。
 * 树的节点总数不会超过 5000。
 *
 *
 * @ProjectName: leetcode
 * @Package: com.linyaonan.leetcode.medium._429
 * @ClassName: NAryTreeTraversal
 * @Author: linyaonan
 * @Date: 2020/1/20 14:13
 */
public class NAryTreeTraversal2 {

    public List<List<Integer>> levelOrder(Node root) {
        // 记录数据
        Queue<Node> data = new LinkedList<>();
        List<List<Integer>> result = new ArrayList<>();
        if (root == null) {
            return result;
        }
        data.offer(root);

        while (!data.isEmpty()) {
            int queueSize = data.size();
            List<Integer> currList = new ArrayList<>();
            for(int i = 0; i < queueSize; i++) {
                Node node = data.poll();
                currList.add(node.val);
                if (node.children != null && node.children.size() != 0) {
                    for(Node child : node.children) {
                        data.offer(child);
                    }
                }
            }
            result.add(currList);
        }
        return result;
    }
}
